The present application relates in general to the art of cryptography and more specifically to hardware and techniques for achieving data communications security.
As the electronic transfer of information becomes more and more common, the need to safeguard this information becomes increasingly important. Many large corporations have data-communications systems over which they transmit, or would like to transmit, information of a sensitive nature, whose disclosure could be very detrimental to the corporation. In addition, the Federal Government is becoming increasingly concerned about insuring the individual's right of privacy. For this reason, the Government is already planning security provisions for its own widespread non-military communications networks. Government regulations of the future may impose similar security requirements upon the many types of non-governmental communications.
Perhaps most important of all is the evolution towards the "cashless society" in which transmitted data represents money. Even today many savings banks send monetary transactions through electronic data communications networks and are thus vulnerable to "electronic counterfeiting". Although it has apparently not yet occurred, a highly sophisticated "counterfeiter", with the ability to both monitor and insert data into the communications link, could manipulate such transactions to his advantage.
From the preceding discussion it is apparent that there are two aspects to communications security: confidentiality assurance and integrity assurance. Confidentiality assurance protects the transmitted data against comprehension by anyone who should tap the communications line. In other words, it provides "read" protection. Integrity assurance, on the other hand, protects the transmitted data against being intercepted, modified, and then retransmitted in such a way that the final recipient of the message will receive an intelligible and apparently valid message but one which has in fact been modified. In other words, this aspect of security provides "write" protection.
Properly designed cryptographic equipment can provide for both of these aspects of security. Encryption by its very nature transforms data into an unintelligible form; hence, all well-designed cryptographic equipment provides confidentiality assurance. Although many encryption techniques do not assure integrity, there are cryptographic techniques known which assure both confidentiality and integrity. Typical of such techniques is that disclosed in U.S. Pat. No. 4,159,463, entitled "Communications Line Authentication Device", which is assigned to the same assignee as the present application. Such encryption techniques have the characteristic that any change to any character of the cipher (encrypted traffic) causes subsequent characters of the plain-text (decrypted message) to become garbled (rendered unintelligible). This characteristic is called "garble extension". Therefore, it is possible to develop cryptographic equipment which provides for both of these aspects of security by basing this equipment on an encryption technique which is highly secure and which has the "garble extension" property.
In the prior art, many banks utilized test keys to aid security on telex transfers. In such a case, a bank issues test key procedures to their correspondents with one or more components of those procedures being unique to each correspondent. Components of the message are used in various arithmetical calculations, often including table look-up functions. The numeric result of the calculations is added to the message as a test key (or authenticator code). The receiver checks the test key by performing the same calculations and using the same components of the message.
An advance over the prior art came in the form of an authenticator device which is somewhat similar to such a test key calculation but offers a level of security many, many times higher. In an authenticator device, the entire message text is used in the calculations and the calculations are based on an algorithm of great complexity. The same algorithm is used by all communicating banks. However, the algorithm also requires an authenticator key variable for its calculations. An authenticator key variable will be agreed upon between two correspondent banks and will not be known to any other party. This unique authenticator key variable ensures that the result of the algorithm can only be generated and/or checked by the sending and receiving banks.
The result of the algorithm, the authenticator code, is added to the trailer of the message. The receiving bank is able to check the authenticator result by using the common algorithm and the unique authenticator key variable agreed to with the sending bank.
In a typical modern communications system where it is desired to verify the integrity of transmitted messages, authenticator devices are normally inserted at both transmitting and receiving ends of the communications line. At the transmitter end, the authenticator device receives a plain text message from the communications line, generates an authenticator code by encrypting the plain text message received and retransmits the plain text message received, with the authenticator code appended thereto, onto the communications line.
At the receiver end, the authenticator device receives the message from the communications line, generates an authenticator code by encrypting the plain text portion of the message received and compares the authenticator code generated with the authenticator code appended to the plain text portion of the message received. If the two authenticator codes are identical, the plain text message has been received exactly as it was transmitted. If the two authenticator codes differ, either an error occurred during transmission of the message or the message has been altered during transmission; viz, the integrity of the message is in doubt.
The authenticator code generator of the present invention operates in two stages. The first stage processes every character in the message and produces a first sequence of 16 check bits called a residue. The primary purpose of the first stage is to preclude "compensating changes"; viz a fraudulent change in the message text associated with another change which has a reasonable probability of compensating for the first change in such a way that the authenticator code of the original message would be valid for the modified message. The second stage processes this 16 bit residue and transforms it, in a highly complex manner, into a second sequence of 16 check bits (the authenticator code). The primary purpose of the second stage is to prevent determination of the authenticator key variable by cryptoanalytical techniques.
The generator provides a very high degree of security against the two above mentioned threats to which the generator is exposed: compensating text modifications, and cryptoanalytical key determination. The former requirement is in many ways the more difficult to fulfill, as many generators for which the key variable is virtually impossible to determine can be circumvented by making compensating text modifications. In such case, the would-be counterfeiter can make a simple change in the text (perhaps to the leading digit of an amount field), and then, from a knowledge of the device's operation but not the key variable, determine another change which has a reasonable probability of compensating for the first change so that the original authenticator code is still valid. It is an object of the present invention to be immune to this threat by providing a generator wherein any text modification or combination has only one chance in 65,536 of having the original authenticator code still valid.
The second threat to which an authenticator code generator is exposed is determination of the key variable. The present invention has a "work factor" in excess of 2.times.10.sup.13. The only way to determine a given key variable is by a trial-and-error process of trying all possible keys until the proper one is found. Assuming a very high speed computer which could simulate the authentication code generation apparatus of the present invention so as to process a text character in an average of only 1 microsecond and assuming 150 characters per message, such a computer, operating 24 hours per day, 7 days per week, would require the average of at least 50 years to determine a single authenticator key variable. Possession of a very large number of messages would provide no additional information which could reduce the time for this process.
It is the general object of this invention to provide an improved authenticator code generator for generating a unique authenticator code from the text of a received message.
It is a further object of this invention to provide an improved authenticator code generator for generating a unique authenticator code which is dependent on a key variable stored in the authenticator code generator and the text of a received message.
It is still another object of this invention to provide an authenticator code generation device which provides a very high degree of security against determining the authenticator key variable by cryptoanalytical techniques.
Further, it is an object of this invention to provide an authenticator code generation device which precludes the undetected introduction of compensating type changes in a message.
These and other objects, features and advantages of the present invention will become apparent from the description of the preferred embodiment of the invention when read in conjunction with the drawings contained herewith.